import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:注意寻找尾结点的代码,cur从头结点往后走的代码
 * User: lenovo
 * Date: 2022-08-14
 * Time: 13:58
 */
public class MyLinkedList {
    //内部类
    class Node {
        int data;
        Node next;

        public Node(int val) {
            this.data = val;
        }
    }

    Node head = null;

    //打印
    public void display() {
        if (head == null) {
            System.out.println("空链表");
            return;
        }
        Node cur = head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();

    }

    //size
    public int size() {
        int count = 0;
        Node cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    /**
     * 增加
     * 尾插
     * 头插
     * 任意位置插
     */
    //尾插
    public void lastAdd(int val) {
        //区别于动态数组不用判满
        Node node = new Node(val);
        //空链表
        if (head == null) {
            head = node;
        } else {//非空链表
            Node cur = head;
            //利用循环走到尾巴节点
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    //头插
    public void firstAdd(int val) {
        Node node = new Node(val);
        //空链表
        if (head == null) {
            head = node;
        } else {
            node.next = head;
            head = node;
        }
    }

    //检查index的合法性
    private boolean checkIndex(int index) {
        if (index < 0 || index > size()) {
            return false;
        } else {
            return true;
        }
    }

    public void indexAdd(int index, int val) {
        Node node = new Node(val);
        //空链表
        if (head == null) {
            head = node;
        } else {
            //检查index的合法性
            if (!checkIndex(index)) {
                throw new RuntimeException("index不合法");
            }
            //头插
            if (index == 0) {
                firstAdd(val);
                return;

            }
            if (index == size()) {
                lastAdd(val);
                return;
            }
            //代码走到这里既不是头插也不尾插,且index位置合法
            Node cur = head;
            while (index - 1 != 0) {//cur 走到要插入的节点之前
                cur = cur.next;
                index--;
            }
            node.next = cur.next;
            cur.next = node;
        }
    }


    /**
     * 查找
     */
    public boolean findHave(int val) {
        //空链表
        if (head == null) {
            return false;
        }
        Node cur = head;
        while (cur != null) {
            if (cur.data == val) {
                return true;//看完在往后走
            }
            cur = cur.next;
        }
        //循环走完 没找到
        return false;
    }

    /**
     * 修改
     */
    //检查index的合法性
    public boolean checkUpdateIndex(int index) {
        if (index < 0 || index >= size()) {
            return false;
        }
        return true;
    }

    public void update(int index, int val) {
        //空链表
        if (head == null) {
            return;
        }
        //检查index的合法性
        if (!checkUpdateIndex(index)) {
            throw new RuntimeException("update::index 不合法");
        }
        Node cur = head;
        //找到index处,并且将data修改
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        cur.data = val;


    }

    /**
     * 删除
     * deleteFirst 删除第一次出现的节点
     * deleteAll  删除所有值为val的节点 得遍历整个链表
     */

    //方案一:利用快慢指针
//    public void delete(int val){
//
//        //空链表
//        if(head == null){
//            return ;
//        }
//        //如果val是头结点
//        if(head.data == val){
//            head = head.next;
//            return;
//        }
//        Node cur = head;//cur作为val的前驱节点
//        Node curNext = cur.next;//curNext找val,从头结点的下一个结点开始寻找的
//        while (curNext.data != val){//快慢指针
//           curNext = curNext.next;
//           cur = cur.next;
//        }
//
//
//        //1.cur==null 链表中没有val
//        if(cur == null){
//            return;
//        }
//        //2.curNext == val 找到了跳出循环
//        cur.next = curNext.next;//删除val
//    }
    //方案二:利用链表next域的特点 cur.next.date 前驱可以访问到下一节点的data域
    //寻找val的前驱
    private Node searchPrveOfKey(int val) {
        Node cur = head;
        while (cur.next != null) {//cur.next 一般是会无法访问到尾巴节点,但是while循环里的cur.next.val可以访问到
            if (cur.next.data == val) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    public void delete(int val) {
        //空链表
        if (head == null) {
            return;
        }
        //如果val是头结点
        if (head.data == val) {
            head = head.next;
            return;
        }
        //寻找val的前驱
        Node cur = searchPrveOfKey(val);
        if (cur == null) {
            return;
        } else {
            cur.next = cur.next.next;

        }


    }

    //删除所有值为val的节点
    public void deleteAll(int val) {
        //空链表
        if (head == null) {
            return;
        }
        //如果val是头结点
        if (head.data == val) {
            head = head.next;
        }
        //遍历链表
        Node prev = head;
        Node cur = head.next;
        while (cur != null) {
            if (cur.data == val) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }

        }
        //头结点为空 必须放在最后考虑
        //原因:避免存在开头有连续个节点都为val的情况,因为代码执行到这里为止,除了头结点之外的的节点都被遍历过一遍了
        //如果对头结点的判断放在开始的时候的话,对于开头有连续节点为val的情况,head=head.next,新的头结点又无法被cur=head.next遍历到
        if (head.data == val) {
            head = head.next;
        }
    }

    /***
     * 清空链表
     */
    //暴力清除
    public void clean() {
        head = null;
    }

    //将每个结点都置空 然后在讲头结点置空
    public void cleanEveryNUll() {
        Node cur = head;
        while (cur != null) {
            Node curNext = cur.next;
            cur = null;
            cur = curNext;
        }
        head = null;
    }


    /**
     * 递归实现链表逆序打印
     */
    public void revers(Node head) {
        //空链表
        if(head == null){
            return;
        }

        if (head.next == null) {
            System.out.print(head.data + " ");
            return;
        }
        revers(head.next);
        System.out.print(head.data + " ");
    }

    //获取val值作为节点
    public Node getHead(int val) {
        Node cur = head;
        while (cur != null) {
            if (cur.data == val) {
                return cur;
            }
            cur = cur.next;
        }
        return null;

    }

    /**
     * 栈实现逆序打印
     */
    public void reverse2(){
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        //从头结点开始压栈
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        //从栈顶开始出栈
        while (!stack.empty()){
            Node top = stack.pop();
            System.out.print(top.data+" ");
        }
    }
}
